package com.cat.dataStructure02;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/peaks-in-array/
 * @create 2025/11/1 12:59
 * @since JDK17
 */

class Solution91 {
    class Fenwick {
        int[] tree;
        Fenwick(int n) {
            tree = new int[n + 1];
        }
        void update(int i, int val) {
            while (i < tree.length) {
                tree[i] += val;
                i += i & -i;
            }
        }
        int pre(int i) {
            int ans = 0;
            while (i > 0) {
                ans += tree[i];
                i -= i & -i;
            }
            return ans;
        }
        int query(int l, int r) {
            if (r < l) {
                return 0;
            }
            return pre(r) - pre(l - 1);
        }
    }
    public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
        int n = nums.length;
        Fenwick f = new Fenwick(n);
        for (int i = 1; i < n - 1; i++) {
            update(f, nums, i, 1);
        }
        List<Integer> ans = new ArrayList<>();
        for (var q : queries) {
            if (q[0] == 1) {    // 直接计算答案
                ans.add(f.query(q[1] + 1, q[2] - 1));
                continue;
            }
            int i = q[1];
            // 更改这一个位置会影响它以及周围的两个位置
            // 撤销之前的答案
            for (int j = Math.max(i - 1, 1); j <= Math.min(i + 1, n - 2); j++) {
                update(f, nums, j, -1);
            }
            nums[i] = q[2];
            // 更新答案
            for (int j = Math.max(i - 1, 1); j <= Math.min(i + 1, n - 2); j++) {
                update(f, nums, j, 1);
            }
        }

        return ans;
    }


    void update(Fenwick f, int[] nums, int i, int val) {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
            f.update(i, val);
        }
    }
}